package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/9/20 17:05
 */
public class _45_跳跃游戏_2 {
    public static void main(String[] args) {
        int[] nums = new int[]{2,3,1,1,4};
        System.out.println(jump(nums));
    }
    public static int jump(int[] nums) {
        if (nums.length <= 1){
            return 0;
        }
        //定义计数器
        int cnt = 0;
        //定义当前范围所能到达的最大值
        int curDistance = 0;
        //定义当前范围中的最大值，当时机成熟，赋值给curDistance
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            //从左向右遍历，获取遍历的每一个角标下i的最远距离
            maxDistance = Math.max(maxDistance,i+nums[i]);
            //如果当前i下，恰好能达到终点，则在跳一步
            if (maxDistance >= nums.length - 1){
                return ++cnt;
            }
            //如果达到了当前步数的最大范围，说明这一步再走下一步无法抵达终点，我们取能达到最远距离的角标
            if (i == curDistance){
                curDistance = maxDistance;
                cnt++;
            }
        }
        return cnt;
    }
}
